// 需要收集任何两个点之间的最短距离
// 然后列出所有的组合, 最终求出最短路线
// 最后要回到起点
const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
let n, m; // n表示客户到站点信息数, m表示客户到客户信息数
let initArr = [];
let customerArr = []; // 客户之间的连接信息
let map = new Map()
let index = 1; // 客户编码转为索引
rl.on("line", (line)=>{
    if(n === undefined) {
        [n, m] = line.trim().split(" ").map(Number)
    } else if (initArr.length < n) {
        const [a, c] = line.trim().split(" ").map(Number)
        map.set(a, index);
        initArr.push([0, index, c])
        index++;

        if(initArr.length === n && m === 0) {
            console.log(getResult(initArr, customerArr))

            // clear
            n = m = undefined
            initArr.length = 0
            customerArr.length = 0
            map.clear()
            index = 1
        }

    } else {
        const [a, b,  c] = line.trim().split(" ").map(Number)
        customerArr.push([map.get(a), map.get(b), c])
        if(customerArr.length === m) {
            console.log(getResult(initArr, customerArr))

            // clear
            n = m = undefined
            initArr.length = 0
            customerArr.length = 0
            map.clear()
            index = 1
        }
    }
})

function getResult(initArr, customerArr) {
    let n = initArr.length + 1
    let dp = new Array(n).fill(null).map(_ => new Array(n).fill(Infinity))
    for (let i = 0; i < dp.length; i++) {
        dp[i][i] = 0
    }

    // 填充数据
    for (const [a, b, c] of initArr) {
        dp[a][b] = c
        dp[b][a] = c
    }
    for (const [a, b, c] of customerArr) {
        dp[a][b] = c
        dp[b][a] = c
    }

    // 填充剩余数据 flod
    for (let i = 0; i < n ; i++) {
        for (let j = 0; j < n; j++) {
            for (let k = 0; k < n; k++) {
                dp[j][k] = Math.min(dp[j][k], dp[j][i] + dp[i][k])
            }
        }
    }

    let arr = []
    // 求所有组合
    let used = new Array(n).fill(false)
    backTrack(n - 1, [], arr, used)

    let ans = Infinity
    // 组合求解
    for (const ele of arr) {
        let before = 0
        let temp = 0
        for (const num of ele) {
            temp += dp[before][num]
            before = num
        }
        temp = dp[before][0] + temp
        ans = Math.min(ans , temp)
    }
    return ans
}

function backTrack(n, path, arr, used) {
    if(path.length === n) {
        arr.push([ ...path])
        return
    }

    for (let i = 1; i <= n ; i++) {
        if(used[i] === false) {
            used[i] = true
            path.push(i)
            backTrack(n, path, arr, used)
            used[i] = false
            path.pop()
        }
    }
}